package org.aplombh.java.leetcode.all;

import java.util.ArrayList;
import java.util.List;

public class _17电话号码的字母组合 {
    public static void main(String[] args) {
        List<String> list = new Solution17_1().letterCombinations("23");
        for (String s : list) {
            System.out.println(s);
        }
    }
}


class Solution17_1 {

    List<String> ans = new ArrayList<>();
    char[][] pat = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};

    public List<String> letterCombinations(String digits) {

        if (digits.equals(""))
            return ans;

        backtrack(digits, 0, new StringBuffer());

        return ans;
    }

    /**
     * 回溯
     *
     * @param digits 原数组
     * @param index  第几位
     * @param sb     字符串
     */
    public void backtrack(String digits, int index, StringBuffer sb) {

        if (index == digits.length()) {
            ans.add(sb.toString());
            return;
        }
        char[] chars = pat[digits.charAt(index) - 2 - '0'];
        for (char aChar : chars) {

            backtrack(digits, index + 1, sb.append(aChar));
            // 回溯
            sb.deleteCharAt(sb.length() - 1);

        }

    }
}